Codeforces Round 499 (Div. 2)

充分认识到水平低下，学习习惯差的弱小

交互题不会、gcd不会

---

A、B

签到

---

C

强行给自己加戏， FST

---

D

---

E

题意

给你n个十进制进制的数，问转化为k进制后，每个数可以使用无数次，问个位数0~k可以组成那些数

题解

贝祖定理

记 $gcd(k, a_1, a_2, …) = d$,然后所有的这些值都除个 $d$ , $gcd$ 就变成 $1$ 了,考虑$gcd(a, b) = 1$，则可以找到很多组$s, t$，使得
$s·a + t ·b = 1$， 这样组一组就有 $s · k + t_1 ·a_1 + t_2 · a_2 + … = 1$，考虑模 $k$ 的情况，$s · k$ 就没了，$t_i$也可以全部转到非负数范围内,这样就能找到一组交钱的方式，可以让税变成最低位为$1$, 那就能组出来 $0$ ~ $k/d$ 的所有情况了,所以答案是:

$$k/d$$

$$0 · d, 1 · d, 2 · d, …$$

update:

根据扩展欧里几得算法可得：

若$gcd(a,k)=1$,则$(a*n)$ % $k$一定可以取到$[0,k-1]$的所有数($n$为正整数)